The present invention relates to a method for compressing image information at a high speed and a method for transferring real-time moving images utilizing the same that makes it possible to generate dynamic compression and transmission sleds.
An example of a group of curves referred to as xe2x80x9cspace filling curvesxe2x80x9d is Hilbert curves proposed by D. Hilbert in 1891, and a method for compressing image information using scanning of two-dimensional Peano curve that is similar thereto has been proposed (see JP-B-7-22345).
FIG. 1 is a diagram showing examples of conventional two-dimensional Hilbert curves in which FIG. 1(a) shows a case of 2xc3x972 pixels; FIG. 1(b) shows a case of 4xc3x974 pixels; and FIG. 1(c) shows a case of 8xc3x978 pixels.
Such curves are recently applied to various researches covering classification of spectral images, database information searching, image compression, computer holograms and the like because of their high neighborhood retaining properties. In such applications, Hilbert curves are used for processing data distributed in two-dimensional and three-dimensional spaces. In general, an operation of establishing one-to-one correspondence between lattice points in an N-dimensional space (N=2, 3, . . .) and one-dimensional points is referred to as xe2x80x9cscanningxe2x80x9d, and scanning along a Hilbert curve is referred to as xe2x80x9cHilbert scanningxe2x80x9d.
Articles on the prior art relating to methods for compressing image information include:
(1) T. Agui, T. Nagae and M. Nakajima, xe2x80x9cGeneralized Peano Scans for Arbitrary-sized Arraysxe2x80x9d, ITEJ Technical Report Vol. 14, No. 37, pp. 25-30, July 1990
(2) Y. Bandoh and S. Kamata, xe2x80x9cA Method of computing a Pseudo-Hilbert Scan Filling in a Rectangular parallelepiped Regionxe2x80x9d, IEICE Transactions (D-II), Vol. J80-D-II, No. 10, pp. 2864-2867, October, 1997
(3) S. Kamata, A. Perez, E. Kawaguchi, xe2x80x9cA Method of Computing Hilbert curves in Two- and Three-Dimensional Spacesxe2x80x9d, IEICE Transaction (D-II), Vol. J74-D-II, No. 9, pp. 1217-1226, September 1991.
(4) X. Liu, G. F. Schrack, xe2x80x9cAn Algorithm for Encoding and Decoding the 3-D Hilbert Orderxe2x80x9d, IEEE Trans. Image Processing, IP-6, No. 9, pp. 1333-1337, September 1997
However, the use of Hilbert scanning has a problem in that the range of application is limited to regions in regions in an N-dimensional space that satisfies:       N          ⏞                        2                      m            x                          ⁢                  …                                    xe2x80x83                        ⁢            x                          ⁢                  xe2x80x83                ⁢                  2          m                      ⁢      xe2x80x83    ⁢      (          m      ⁢              xe2x80x83            ⁢      is      ⁢              xe2x80x83            ⁢      a      ⁢              xe2x80x83            ⁢      natural      ⁢              xe2x80x83            ⁢      number        )  
On the contrary, normal Hilbert scanning is frequently inapplicable to normal images in which rectangles are to be scanned. Under such circumstances, scanning methods for rectangular parallelepiped regions have been proposed as generalization of two-dimensional Hilbert scanning (refer to the above-cited articles (1) and (2) on the prior art). The method according to the article (1) on the prior art still has problems associated with computing time and implementation on a hardware basis because it is a method based on a recursive process.
On the contrary, the method according to the article (2) on the prior art proposed by the inventors is a scanning method at a high speed which is an extended version of the article (3) on the prior art including no recursive process. According to the articles (2) and (3) on the prior art, rules for the generation of Hilbert curves are formed into a table in advance, and it is referred one after another to eliminate recursion.
Such generalization of Hilbert scanning has not been considered for three-dimensional applications because of complicated calculations associated therewith. The method according the article (1) on the prior art is generalization of two-dimensional Hilbert scanning, and no specific method for three-dimensional applications is described. The method according to the article (4) on the prior art remains in a computing method in a cubic region (2mxc3x972mxc3x972m), and nothing is mentioned about a case of rectangular parallel piped region. Therefore, the application of Hilbert scanning to three-dimensional spaces has been strictly limited.
However, the generalization of Hilbert scanning in a three-dimensional space can be carried out similarly to that in a two-dimensional space based on the technique according to the article (2) on the prior art.
Under the above-described circumstances, it is a first object of the invention to provide a method for compressing image information at a high speed and a system for compressing image information in which scanning is carried out on rectangular parallelepiped regions (without being limited to three-dimensional Hilbert scanning) as extension of three-dimensional Hilbert scanning to improve throughput and to achieve cost reduction. The utilization of Hilbert curves for scanning of rectangular parallelepiped regions is referred to as xe2x80x9cpseudo Hilbert scanningxe2x80x9d.
In conventional systems for transferring and distributing moving images, moving images compressed at a distributing server in advance have been transmitted with quality and at a speed determined at the server.
FIG. 2 shows an example of a processing flow in such a conventional system in which image signals from a television camera are fetched into a computer at constant intervals with means such as video capture, and the fetched images are subjected to image compression to transmit image data. A personal computer at the receiving end decompresses the compressed images to display an image at each update.
However, conventional methods have had the following problems.
(1) In systems such as a television conference, image quality is inevitably reduced because the priority is given to the number of images per unit time. In distribution systems with high image quality, since images are transmitted after they are compressed at the distributing end in advance, image data going to be transmitted represent the past and therefore lose real-time property.
(2) Conventional software compression techniques are not fast enough to perform real-time image compression.
(3) Image compression on a hardware basis is costly because dedicated equipment is required.
(4) Since no consideration is paid to the performance of clients"" end and the conditions of networks, it is not possible to send optimum moving images that meet the requirements of clients.
One reason for such situations is the fact that priority has been given to compression ratios and image quality in conventional compression and decompression techniques over the compression speed because they have been intended for retention and reproduction as typical in the case of DVDs. This has resulted in low compression speeds and has necessitated transmission at the maximum speed. It has therefore been common to sacrifice image quality to speed when moving images are transferred in real-time as in television conference systems.
It is therefore a second object of the invention to achieve the transfer of real-time moving images by compressing and transferring fetched images in real-time, to transfer images optimized for the requirements of clients and the conditions of networks in terms of the image size, the number of images, the intervals (time) between the images and the quality of the images and to generate a compression and transfer sled for each client. This makes it possible to perform optimum transfer of moving images to a plurality of clients under different conditions, to achieve the optimum performance of moving image transfer in adaptation to increased speeds of computers in the future and to achieve transfer of moving images in synchronism with the speed of a network.
In order to achieve the first object, according to the invention, there is provided:
[1] a method for compressing image information at a high speed wherein picked moving images comprising three-dimensional information are converted into one-dimensional serial information one by one using a look-up table associated with rectangular parallelepiped regions in a three-dimensional space and wherein said converted data are subjected to data compression,
[2] a method for compressing image information according to [1], wherein the conversion of the picked moving images into one-dimensional serial information can be performed through three-dimensional pseudo Hilbert scanning,
[3] a method for compressing image information according to [2], wherein rules for recursive division of each side of a rectangular parallelepiped block as the minimum unit for said three-dimensional pseudo Hilbert scanning are defined such that a side having an even length is divided into sides having an even length at a dividing point closest to the mid-point; a side having an odd length is divided into a side having an odd length and a side having an even length at a dividing point closest to the mid-point; and addresses are assigned to the rectangular parallelepiped regions accordingly,
[4] a method for compressing image information according to [2], wherein said data compression is a process of dividing one-dimensional data decompressed through three-dimensional pseudo Hilbert scanning using a threshold,
[5] a method for compressing image information according to [4], wherein said dividing process divides the one-dimensional data into sections that result in the minimum square error from said one-dimensional data and generates compressed data which is linear approximation of each section,
[6] a method for compressing image information according to any of [1] through [5], wherein patterns of differential waveforms between the compressed data and the original data are divided and classified into a plurality of models to prepare error patterns; codes for error patterns that approximate said differential waveforms at the time of data compression are added to the compressed data; and the data are restored by superimposing the waveforms of the error patterns associated with the codes of the relevant error patterns on decompressed data during data decompression,
[7] a system for compressing image information comprising an image pickup device for viewing moving images, three-dimensional pseudo Hilbert scanning means for converting three-dimensional information associated with rectangular parallelepiped regions into one-dimensional serial information, a moving image storage device for storing said one-dimensional serial information and data compression means for compressing data read from the moving image storage device, and
[8] a system for compressing image information comprising an image pickup device for viewing moving images, three-dimensional pseudo Hilbert scanning means for converting three-dimensional information associated with rectangular parallelepiped regions into one-dimensional serial information, a moving image storage device for storing said one-dimensional serial information, data compression means for compressing data read from the moving image storage device, a reversible encoding portion for the compressed data, a transmission path for compressed data from the reversible encoding portion, a reversible decoding portion for the transmitted compressed data, a portion for restoring data from the reversible decoding portion, a second moving image storage device for storing data from the data restoring portion, three-dimensional pseudo Hilbert scanning means associated with the rectangular parallelepiped regions for scanning compressed data read from the moving image storage device and a display device for displaying output moving images.
In order to achieve the second object, according to the invention, there is provided:
[9] a method for transferring viewed moving images from a server to clients in real-time, wherein viewed moving images comprising three-dimensional information are converted into one-dimensional serial information one by one using a look-up table associated with rectangular parallelepiped regions in a three-dimensional space and wherein the converted original data are compressed using a software compression technique and are transferred through a communication path,
[10] a method for transferring real-time moving images according to [9], wherein patterns of differential waveforms between the compressed approximate data and the original data are divided and classified into a plurality of models to prepare error patterns at each of the server and clients; codes for error patterns that approximate the differential waveforms at the time of data compression at the server are transferred to the clients along with the compressed data; and the data are restored by superimposing the waveforms of relevant error patterns on decompressed data during data decompression at the clients,
[11] a method for transferring real-time moving images according to [9] or [10], wherein a look-up table is dynamically generated upon a request from a client,
[12] a method for transferring real-time moving images according to [11], wherein a look-up table is used on which any image size can be specified as requested by a client,
[13] a method for transferring real-time moving images according to [11] or [12], wherein a look-up table is used on which any number of images can be specified as requested by a client,
[14] a method for transferring real-time moving images according to [9], wherein the compression ratio of an image is changed as requested by a client,
[15] a method for transferring real-time moving images according to any of [9] through [14], wherein a specific compression and transfer sled is generated to each request by a client,
[16] a method for transferring real-time moving images according to any of [9] through [15], wherein intervals between images are changed as requested by a client, and
[17] a method for transferring real-time moving images according to any of [9] through [16], wherein management means is provided for processing a request from each of a plurality of clients simultaneously.